package sort;

/**
 * @author qiss
 * @create 2018-04-20 10:22
 * https://blog.csdn.net/happy_wu/article/details/51841244
 **/
public class QuickSort {
    public static void main(String[] args) {
        int[] array = {1,5,2,21,3,9,0,12,7,8,4,3,10};
        print(array);
        quickSort(array,0,array.length-1);
        print(array);
    }

    private static void quickSort(int[] array, int left, int right) {
        int pivot = 0;
        if(left < right){
            pivot = partition3(array,left,right);
            quickSort(array,left,pivot-1);
            quickSort(array,pivot+1,right);
        }
    }

    private static int partition(int[] array, int left, int right) {
        int i,j,temp;
        j=left-1;
        for (i=left;i<=right;i++){
            if(array[i] <= array[right]){
                j++;
                temp = array[j];
                array[j] = array[i];
                array[i] = temp;
            }
        }
        print(array);
        return j;
    }

    private static int partition2(int[] array, int left, int right) {
        int temp = array[left];
        while (left < right){
            while (array[right] >= temp && right>left){
                right--;
            }
            array[left] = array[right];     //变相交换位置
            while (array[left] <= temp && left<right){
                left++;
            }
            array[right] = array[left];
        }
        array[right] = temp;
        print(array);
        return left;
    }


    private static int partition3(int[] array,int low,int high){
        int i = low;
        int j = high;
        int key = array[low];
        while (i < j){
            while (i<j && array[j] > key){
                j--;
            }
            while (i<j && array[i] <= key){
                i++;
            }
            if(i<j){
                int p = array[i];
                array[i] = array[j];
                array[j] = p;
            }
        }
        int p = array[i];
        array[i] = array[low];
        array[low] = p;
        return i;
    }

    /**
     * 时间复杂度 O（n^2）
     * @param a
     */
    private static void insertSort(int[] a){
        //从头部第一个当做已经排好序的，把后面的逐个插入排好的列表中
        for (int i = 1; i < a.length; i++) {
            int j;
            int x = a[i];  //待插入元素
            for(j = i; x < a[j-1] && j > 0;j--){  //后移一位比较
                a[j] = a[j-1];
            }
            a[j] = x;//插入
        }
    }



    private static void print(int[] array){
        for (int n = 0; n < array.length; n++) {
            System.out.print(array[n]+",");
        }
        System.out.println("");
    }
}
